package week_07;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 918. 环形子数组的最大和
 * 给定一个由整数数组 A 表示的环形数组 C，求 C 的非空子数组的最大可能和。
 * <p>
 * 在此处，环形数组意味着数组的末端将会与开头相连呈环状。
 * （形式上，当0 <= i < A.length 时 C[i] = A[i]，且当 i >= 0 时 C[i+A.length] = C[i]）
 * <p>
 * 此外，子数组最多只能包含固定缓冲区 A 中的每个元素一次。
 * （形式上，对于子数组 C[i], C[i+1], ..., C[j]，不存在 i <= k1, k2 <= j 其中 k1 % A.length = k2 % A.length）
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：[1,-2,3,-2]
 * 输出：3
 * 解释：从子数组 [3] 得到最大和 3
 * 示例 2：
 * <p>
 * 输入：[5,-3,5]
 * 输出：10
 * 解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
 */
public class MaxSubarraySumCircular_918 {

    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        int[] copy = new int[2 * n];
        for (int i = 0; i < n; i++) {
            copy[i] = nums[i];
            copy[n + i] = nums[i];
        }
        int[] sums = new int[2 * n + 1];
        sums[0] = 0;
        for (int i = 0; i < 2 * n; i++) {
            sums[i + 1] = sums[i] + copy[i];
        }

        Deque<Integer> deque = new LinkedList<>();
        deque.add(0);
        int ans = Integer.MIN_VALUE;
        for (int i = 1; i <= 2 * n; i++) {
            // 去掉不合法的对头 i-j<=n
            while (!deque.isEmpty() && i - deque.getFirst() > n) deque.removeFirst();
            if (!deque.isEmpty()) ans = Math.max(sums[i] - sums[deque.getFirst()], ans);
            // 队列里放最小的前缀和，保持单调递增的趋势
            while (!deque.isEmpty() && sums[deque.getLast()] >= sums[i]) deque.removeLast();
            deque.add(i);

        }
        return ans;
    }

    public int maxSubarraySumCircular_1(int[] nums) {

        int n = nums.length;
        int[] sums = new int[n + 1];
        sums[0] = 0;
        for (int i = 0; i < n; i++) {
            sums[i + 1] = sums[i] + nums[i];
        }
        // 结果两种可能：
        // case1: 结果没有跨环（最大子段和）
        int ans = Integer.MIN_VALUE;
        int preMinSum = sums[0];
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, sums[i] - preMinSum);
            preMinSum = Math.min(preMinSum, sums[i]);
        }
        // case2: 结果跨环 (数组和 - 最小子段和)
        // 前缀和 - 之前的最大的前缀和 = 最小的字段和
        int minSum = Integer.MAX_VALUE;
        int preMaxSum = sums[0];
        for (int i = 1; i < n; i++) {
            minSum = Math.min(minSum, sums[i] - preMaxSum);
            preMaxSum = Math.max(preMaxSum, sums[i]);
        }
        // 处理最小和的边界 n
        preMaxSum = sums[1];
        // 单独找出->全负数 最大 前缀和 再计算一次 最小子段和
        for (int i = 2; i <= n; i++) preMaxSum = Math.max(preMaxSum, sums[i]);
        if (n > 1) minSum = Math.min(minSum, sums[n] - preMaxSum);

        return Math.max(ans, sums[n] - minSum);
    }
}
